package datastructure.lru;

import java.util.*;


/**
 * 第二次重写
 * 双向链表 + Map
 *  初始属性size  capacity  head tail
 * 注意点
 *  1. node需要有key属性 方便removeTail的时候 从map中remove掉
 *  2. put 可以更新  也能新增
 */
class LRUCache {


    Map<Integer, DoubleLinkedListNode> lruMap;
    DoubleLinkedListNode head;
    DoubleLinkedListNode tail;
    int capacity, size = 0;

    public LRUCache(int capacity) {
        lruMap = new HashMap<>(capacity);
        head = new DoubleLinkedListNode(-1,-1);
        tail = new DoubleLinkedListNode(-1,-1);
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
    }

    public int get(int key) {
        DoubleLinkedListNode node = lruMap.get(key);
        if (node == null) return -1;
        moveToHead(node);
        return node.val;
    }

    public void put(int key, int value) {
        DoubleLinkedListNode node = lruMap.get(key);
        // 不是已经存在 往头部塞一个  注意更新size
        if(node == null) {
            // remove tail
            if (size == capacity) {
                int keyToBeRemoved = removeTail();
                lruMap.remove(keyToBeRemoved);
                size --;
            }
            // insert head
            node = new DoubleLinkedListNode(key, value);
            insertToHead(node);
            lruMap.put(key, node);
            size ++;
        } else {
            // 更新值
            node.val = value;
            moveToHead(node);
        }

    }

    private void moveToHead(DoubleLinkedListNode node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        insertToHead(node);
    }

    private int removeTail() {
        if (head.next == tail) return -2;
        DoubleLinkedListNode toBeRemoved = tail.prev;
        DoubleLinkedListNode prev = toBeRemoved.prev;
        prev.next = tail;
        tail.prev = prev;
        return toBeRemoved.key;
    }

    private void insertToHead(DoubleLinkedListNode node) {
        DoubleLinkedListNode next = head.next;
        head.next = node;
        node.next = next;
        next.prev = node;
        node.prev = head;
    }

    class DoubleLinkedListNode {
        int key,val;
        DoubleLinkedListNode prev;
        DoubleLinkedListNode next;

        public DoubleLinkedListNode(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

}

class LRUCache_146 {

            // 需要在 O(1) 时间复杂度中拿到元素  以及 O(1) 时间复杂度内插入元素 
            //   get很容易想到用map来拿 但是put如果是O(1) 时间复杂度的话就只能是链表了  
            //  因此本题就是 *****   哈希链表  ****** LinkedHashMap就是这种
            //  为什么要是双向链表，单链表行不行？另外，既然哈希表中已经存了 key，为什么链表中还要存键值对呢，只存值不就行了？
            //        需要从链表中间删除某个节点  O(1) 时间查找前驱节点只能用双端   删除节点的同时要返回去删除map中的key
            
            private HashMap<Integer, DoubleEndListNode> map;
            //  head在左  tail 在右  按照这个方向 看 前后
            private DoubleEndListNode head = new DoubleEndListNode(0,0),
                                      tail = new DoubleEndListNode(0,0);
            private int capacity, 
                        size = 0;
            public LRUCache_146(int capacity) {
                this.capacity = capacity;
                this.map = new HashMap<>(capacity);
                head.next = tail;
                tail.prev = head;
            }
            
            //  get ：     移除元素放到队首
            public int get(int key) {
                if(map.containsKey(key)){
                    final DoubleEndListNode node = map.get(key);
                    remove(node);
                    addFirst(node);
                    return node.val;
                }
                return  -1;
            }

            /**
      * 没有就修改key对应的value
      * 两种操作  更新 ：移除元素放到队首   新增： 放到队首
      */
            public void put(int key, int value) {
                final DoubleEndListNode doubleEndListNode = map.get(key);
                if(doubleEndListNode == null) {
                    if(size == capacity){
                        final DoubleEndListNode nodeRemoved = removeTail();
                        map.remove(nodeRemoved.key);
                        size--;
                    }
                    final DoubleEndListNode node = new DoubleEndListNode(key, value);
                    addFirst(node);
                    map.put(key, node);
                    size ++;
                } else {
                    doubleEndListNode.val = value;
                    remove(doubleEndListNode);
                    addFirst(doubleEndListNode);
                }
                
                
            }
           

            //  put操作   插入到head和队首元素之间
            public void addFirst(DoubleEndListNode node) {
                node.prev = head;
                node.next = head.next;
                head.next.prev = node;
                head.next = node;
            }

            // put操作
            public void remove(DoubleEndListNode node) {
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }

            /**
      * 队列满了 移除tail的元素  再put  
      * 有虚拟头尾节点 需要返回目标节点
      */
            public DoubleEndListNode removeTail() {
                DoubleEndListNode node = tail.prev;
                node.prev.next = tail;
                tail.prev = node.prev;
                return node;
            }

            // 双端链表节点
            class DoubleEndListNode{
                int key;
                int val;
                DoubleEndListNode prev;
                DoubleEndListNode next;

                public DoubleEndListNode(int key, int val) {
                    this.key = key;
                    this.val = val;
                }
            }

        }

/**
  * Your LRUCache object will be instantiated and called as such:
  * LRUCache obj = new LRUCache(capacity);
  * int param_1 = obj.get(key);
  * obj.put(key,value);
  */


class LRUCache_<K,V> implements Iterable<K> {

    private LinkedHashMap<K,V> cache ;
    int capacity;
    public LRUCache_(int capacity) {
        this.capacity = capacity;
        cache = new LinkedHashMap<>(capacity, 0.75f, true); // 加上 true   会在get的时候将元素e重新加入到头部
    }
    public void put(K key, V value) {
        if(cache.containsKey(key)) {    // 移除已存在的
            cache.remove(key);
        } else if(cache.size() == capacity) { // 移除最左边的
            Iterator<K> keySet = cache.keySet().iterator();
            if(keySet.hasNext()) {
                cache.remove(keySet.next());
            }
        }
        cache.put(key, value);   // 从头部重新插入
    }

    public V get(K key, V value) {
        V v = cache.get(key);
        if(v == null) return null;
        return v;
    }

    @Override
    public Iterator<K> iterator() {
        Iterator<Map.Entry<K,V>> it = cache.entrySet().iterator();
        return new Iterator<K>() {
            @Override
            public boolean hasNext() {
                return it.hasNext();
            }

            @Override
            public K next() {
                return it.next().getKey();
            }
        };
    }
}

